package com.liunian.algorithmstudy.dynamic.subsequence;

public class NumDistinct115 {

	/**
	 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。

	 示例 1：
	 输入：s = "rabbbit", t = "rabbit"
	 输出：3
	 解释：
	 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。

	 					t
	             r   a   b   b   i   t
	        ----------------------------
	        | 1  0   0   0   0   0   0       	在空里出现‘r’、'ra'、'rab'、'rabb'、'rabbi'、'rabbit'的次数都是0
	       r| 1  1   0   0   0   0   0
	       a| 1  1   1   0   0   0   0
       s   b| 1  1   1   1   0   0   0
	       b| 1  1   1   2   1   0   0
	       b| 1  1   1   3   3   0   0
	       i| 1  1   1   3   3   3   0
	       t| 1  1   1   3   3   3   3
			在‘r’、'ra'、'rab'、'rabb'、'rabbb'、'rabbbi'、'rabbit'中出现啥都没有的次数都是1
	 示例 2：
	 输入：s = "babgbag", t = "bag"
	 输出：5
	 解释：
	 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
	 */
	public int numDistinct(String s, String t) {
		int[][] dp = new int[s.length() + 1][t.length() + 1];
		for (int i = 0; i < s.length() + 1; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i < s.length() + 1; i++) {
			for (int j = 1; j < t.length() + 1; j++) {
				if (s.charAt(i - 1) == t.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				} else {
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		return dp[s.length()][t.length()];
	}

	public static void main(String[] args) {
		NumDistinct115 numDistinct115 = new NumDistinct115();
		System.out.println(numDistinct115.numDistinct("rabbbit", "rabbit"));
	}

}
